Proposition 2.5 is a direct consequence of the following lemma (remember that Lemma A.1 (Smooth functions conserved through a given flow.) . Assume that @h () ()=0 for all 2 . Let us first show the direct inclusion. Now let us show the converse inclusion. We recall (cf Example 2.10 and Example 2.11) that linear and Assumption 2.9, which we recall reads as: Theorem 2.14, let us show that (9) holds for standard ML losses.

Then OMAC (Algorithm 1) specifiedby Table 3 hasthe followingACEguarantee (withprobabilityatleast1 ): ACE 1 r W2+ o(T) T +O( log (NT / ) log (N) N ).

Forthis, wefirstconsiderthe -trickon(18), inwhichwesetw(t)= w+(t) w (t) where log w+(t)= rwL(w(t)), log w (t)=+ rwL(w(t)).